package structure.tree;

import java.util.Objects;

public class BinaryTree {
    /** 根节点 */
    private BinaryTreeNode root;

    /**
     * 以根节点构造一个二叉树
     * @param root
     */
    BinaryTree(BinaryTreeNode root) {
        if (root.getLeftChild() == null && root.getRightChild() == null) {
            this.root = root;
        } else {
            System.out.println("构造二叉树失败：根节点的左右子节点不是空的");
        }
    }

    /** 初始化二叉树的所有节点 */
    private void initializeAllNodes() {
        BinaryTreeNode temp = root;
        // 当该节点至少有一个子节点不为空且这个子节点已读时
        while (Objects.requireNonNull(temp).getLeftChild() != null && temp.getLeftChild().isRead() || temp.getRightChild() != null && temp.getRightChild().isRead()) {
            BinaryTreeNode tempParent = temp;
            temp = temp.getLeftChild();
            if (temp != null && temp.isRead()) {
                temp = initializeNode(temp);
            } else if (tempParent.getRightChild() != null && tempParent.getRightChild().isRead()) {
                temp = tempParent.getRightChild();
                temp = initializeNode(temp);
            }
        }
        temp.setEnabled(true);
        temp.setRead(false);
    }

    /**
     * 初始化目标节点的所有子节点
     * @param temp
     * @return
     */
    private BinaryTreeNode initializeNode(BinaryTreeNode temp) {
        // 如果该节点没有子节点
        if (temp.getLeftChild() == null && temp.getRightChild() == null) {
            initializeCurrentNode(temp);
            temp = root;
            // 否则如果该节点有两个子节点
        } else if (temp.getLeftChild() != null && temp.getRightChild() != null) {
            // 如果两个子节点均未读
            if (!temp.getLeftChild().isRead() && !temp.getRightChild().isRead()) {
                initializeCurrentNode(temp);
                temp = root;
            }
            // 如果左子节点存在且未读
        } else {
            if (temp.getLeftChild() != null && !temp.getLeftChild().isRead()) {
                initializeCurrentNode(temp);
                temp = root;
                // 否则如果右子节点存在且未读
            } else if (temp.getRightChild() != null && !temp.getRightChild().isRead()) {
                initializeCurrentNode(temp);
                temp = root;
            }
        }
        return temp;
    }

    /**
     * 将目标节点设置为可用和未读
     * @param temp
     */
    private void initializeCurrentNode(BinaryTreeNode temp) {
        temp.setEnabled(true);
        temp.setRead(false);
    }

    /**
     * 查找指定节点
     * @param node
     * @return
     */
    boolean find(BinaryTreeNode node) {
        initializeAllNodes();
        BinaryTreeNode temp = root;
        // 将节点设置为已读
        temp.setRead(true);
        if (temp.equals(node)) {
            return true;
        } while (Objects.requireNonNull(temp).getLeftChild() != null && temp.getLeftChild().isEnabled() || temp.getRightChild() != null && temp.getRightChild().isEnabled()) {
            BinaryTreeNode tempParent = temp;
            // 转到当前节点的左子节点
            temp = temp.getLeftChild();
            if (temp != null && temp.isEnabled()) {
                temp.setRead(true);
                if (temp.equals(node)) {
                    return true;
                }
                temp = recursiveFind(temp);
            } else if (tempParent.getRightChild() != null && tempParent.getRightChild().isEnabled()) {
                // 转到当前左子节点的兄弟节点（父节点的右子节点）
                temp = tempParent.getRightChild();
                temp.setRead(true);
                if (temp.equals(node)) {
                    return true;
                }
                temp = recursiveFind(temp);
            }
        }
        temp.setEnabled(false);
        return false;
    }

    private BinaryTreeNode recursiveFind(BinaryTreeNode temp) {
        // 如果该节点没有子节点
        if (temp.getLeftChild() == null && temp.getRightChild() == null) {
            // 将该节点设置为不可用
            temp.setEnabled(false);
            // 返回根节点
            temp = root;
        } else if (temp.getLeftChild() != null && temp.getRightChild() != null) {
            if (!temp.getLeftChild().isEnabled() && !temp.getRightChild().isEnabled()) {
                temp.setEnabled(false);
                temp = root;
            }
        } else {
            if (temp.getLeftChild() != null && !temp.getLeftChild().isEnabled()) {
                temp.setEnabled(false);
                temp = root;
            } else if (temp.getRightChild() != null && !temp.getRightChild().isEnabled()) {
                temp.setEnabled(false);
                temp = root;
            }
        }
        return temp;
    }

    /**
     * 在指定节点的指定一侧插入子节点
     * @param parent
     * @param location
     * @param child
     */
    void insert(BinaryTreeNode parent, boolean location, BinaryTreeNode child) {
        if (!find(parent) || find(child)) {
            System.out.println("插入节点失败：没有找到父节点" + parent.getName() + "或预插入的子节点" + child.getName() + "已是某个节点的子节点");
        } else {
            if (parent.getLeftChild() != null && parent.getRightChild() != null) {
                System.out.println("插入节点失败：父节点" + parent.getName() + "已存在左右子节点");
            } else if (parent.getLeftChild() == null && parent.getRightChild() == null) {
                if (location) {
                    parent.setLeftChild(child);
                } else {
                    parent.setRightChild(child);
                }
            } else {
                if (parent.getLeftChild() == null && location) {
                    parent.setLeftChild(child);
                } else if (parent.getRightChild() == null && !location) {
                    parent.setRightChild(child);
                } else {
                    System.out.println("插入节点失败：节点" + child.getName() + "在父节点" + parent.getName() + "预插入的位置已存在另一个子节点");
                }
            }
        }
    }

    /**
     * 删除指定节点的指定一侧的子节点
     * @param parent
     * @param node
     * @return
     */
    boolean delete(BinaryTreeNode parent, BinaryTreeNode node) {
        boolean status = false;
        if (parent.getLeftChild() == node) {
            recursiveDeleteChild(node);
            parent.setLeftChild(null);
            status = true;
        } else if (parent.getRightChild() == node) {
            recursiveDeleteChild(node);
            parent.setRightChild(null);
            status = true;
        }
        return status;
    }

    /**
     * 递归删除指定节点的所有子节点
     * @param node
     */
    private void recursiveDeleteChild(BinaryTreeNode node) {
        BinaryTreeNode temp = node;
        while (temp.getLeftChild() != null || temp.getRightChild() != null) {
            BinaryTreeNode tempParent = temp;
            temp = temp.getLeftChild();
            if (temp == null) {
                temp = tempParent.getRightChild();
                if (temp.getLeftChild() == null && temp.getRightChild() == null) {
                    tempParent.setRightChild(null);
                    temp = node;
                }
            } else if (temp.getLeftChild() == null && temp.getRightChild() == null) {
                tempParent.setLeftChild(null);
                temp = node;
            }
        }
    }

    /** 遍历二叉树 */
    void display() {
        initializeAllNodes();
        BinaryTreeNode temp = root;
        temp.setRead(true);
        while (Objects.requireNonNull(temp).getLeftChild() != null && temp.getLeftChild().isEnabled() || temp.getRightChild() != null && temp.getRightChild().isEnabled()) {
            BinaryTreeNode tempParent = temp;
            temp = temp.getLeftChild();
            if (temp != null && temp.isEnabled()) {
                temp.setRead(true);
                temp = recursiveDisplay(temp);
            } else if (tempParent.getRightChild() != null && tempParent.getRightChild().isEnabled()) {
                temp = tempParent.getRightChild();
                temp.setRead(true);
                temp = recursiveDisplay(temp);
            }
        }
        if (!temp.isEnabled()) {
            if (temp.getLeftChild() != null && temp.getRightChild() != null) {
                System.out.println("节点" + temp.getName() + "的左子节点为" + temp.getLeftChild().getName());
                System.out.println("节点" + temp.getName() + "的右子节点为" + temp.getRightChild().getName());
            } else {
                if (temp.getLeftChild() != null) {
                    System.out.println("节点" + temp.getName() + "的左子节点为" + temp.getLeftChild().getName());
                } else if (temp.getRightChild() != null) {
                    System.out.println("节点" + temp.getName() + "的右子节点为" + temp.getRightChild().getName());
                }
            }
        }
        temp.setEnabled(false);
    }

    /**
     * 递归遍历指定节点及其所有子节点
     * @param temp
     * @return
     */
    private BinaryTreeNode recursiveDisplay(BinaryTreeNode temp) {
        if (temp.getLeftChild() == null && temp.getRightChild() == null) {
            temp.setEnabled(false);
            temp = root;
        } else if (temp.getLeftChild() != null && temp.getRightChild() != null) {
            if (!temp.getLeftChild().isEnabled() && !temp.getRightChild().isEnabled()) {
                System.out.println("节点" + temp.getName() + "的左子节点为" + temp.getLeftChild().getName());
                System.out.println("节点" + temp.getName() + "的右子节点为" + temp.getRightChild().getName());
                temp.setEnabled(false);
                temp = root;
            }
        } else {
            if (temp.getLeftChild() != null && !temp.getLeftChild().isEnabled()) {
                System.out.println("节点" + temp.getName() + "的左子节点为" + temp.getLeftChild().getName());
                temp.setEnabled(false);
                temp = root;
            } else if (temp.getRightChild() != null && !temp.getRightChild().isEnabled()) {
                System.out.println("节点" + temp.getName() + "的右子节点为" + temp.getRightChild().getName());
                temp.setEnabled(false);
                temp = root;
            }
        }
        return temp;
    }
}
